{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm design and anlysis-2025 spring  homework 3\n",
    "**Deadline**：2025.5.14\n",
    "\n",
    "**name**:\n",
    "\n",
    "\n",
    "note：\n",
    "---\n",
    "1. 带有\\*的题目，申请免上课的同学，必须完成，其他同学选作；\n",
    "2. 请独立完成，如求助了他人或者大模型，请著明，并且不可省略算法分析部分；\n",
    "4. 如若作答有雷同，全部取消成绩；\n",
    "3. 需要书面作答的题目，可以通过引用图片的形式添加，但是注意上传项目时包含所引用的图片的源文件；\n",
    "4. $log_n$ 默认表示$log_2{n}$;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 1  \n",
    "\n",
    "请证明基于比较的排序算法计算复杂度下界为$\\Omega(nlogn)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "you can refer a handwritten picture, pleas upload the picture in /fig/xxx.png\n",
    "answer："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 2 \n",
    "\n",
    "构建二叉搜索树\n",
    "\n",
    "> 1. 给定一个数组 [48, 33, 49, 47, 42, 46, 32], 构建一个二叉搜索树存储这些数据，请**绘制**所构建的**二叉搜索树**（标明结点的值）。\n",
    "> 2. 从第1问的二叉搜索树中删除33，请**绘制**删除33后的**二叉搜索树**（标明结点的值）\n",
    "\n",
    "- 推荐使用graphviz包绘制树的结构"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "you can refer a handwritten picture, pleas upload the picture in /fig/xxx.png\n",
    "answer："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 3 \n",
    "\n",
    "> 下面是九门课程的开始和结束时间:\n",
    ">\n",
    "> [(9:00,12:30), (11:00,14:00), (13:00, 14:30), (9:00,10:30),(13:00, 14:30),(14:00,16:30), (15:00,16:30), (15:00,16:30), (9:00,10:30)]\n",
    ">\n",
    "> 请使用贪婪算法为这九门课分配教室，要求在同一天内安排这些课，并且每个教室同一时间只能安排一门课。\n",
    "\n",
    "**请问最少需要几间教室，罗列出每个教室安排的课程**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "plaintext"
    }
   },
   "outputs": [],
   "source": [
    "code："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 4 \n",
    "\n",
    "> 爬楼梯问题：假设爬楼梯时你每次只能爬一阶或者爬两阶，问爬上n阶的楼梯，你一共有多少种方法\n",
    "\n",
    "请设计算法完成该问题，分析算法设计思路，计算时间复杂度，并基于python编程实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is: "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 5 \n",
    "\n",
    "> 0-1背包问题：现在有4块大理石，每个大理石对应的重量和价值使用一个元组表示, 即（重量，价值），4块大理石的重量和价值为：[(5,10), (4,40), (6,30), (3, 50)], 假设你有一辆最大承重为9的小推车，请问使用这个小推车装大理石的最大价值为多少\n",
    "\n",
    "请设计一个算法解决该问题，分析算法设计思路，计算时间复杂度，并基于python编程实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 6 \n",
    "给定 `n` 个非负整数表示每个宽度为 `1` 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。\n",
    "\n",
    "\n",
    "\n",
    "<div style=\"text-align:center;width:800px;\"> <img alt=\"\" src=\"./fig/hw3q6.png\"> </div>\n",
    "\n",
    "请分析算法设计思路，计算时间复杂度，并基于python编程实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 7 \n",
    "\n",
    "**股票投资组合优化**： 假设你是一位投资者，想要在不同的股票中分配你的资金，以最大化你的投资回报。每只股票都有不同的预期收益率和风险。你的目标是选择一些股票，使得总投资金额不超过你的预算，并且预期收益最大化。\n",
    "\n",
    "在这个情况下，你可以将每只股票视为一个“物品”，其重量为投资金额，价值为预期收益率。然后，你可以使用分级背包问题的方法来选择部分股票，以便在预算内获得最大的预期收益。\n",
    "\n",
    "以下是一个简化的例子：\n",
    "\n",
    "假设你有以下三只股票可供选择：\n",
    "\n",
    "1. 股票 A：投资金额 5000 美元，预期收益率 10%\n",
    "2. 股票 B：投资金额 3000 美元，预期收益率 8%\n",
    "3. 股票 C：投资金额 2000 美元，预期收益率 12%\n",
    "\n",
    "请设计算法找到最优投资方案，分析算法设计思路，计算时间复杂度，并基于python编程实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 8\n",
    "\n",
    "给你二叉搜索树的根节点 root ，该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。设计算法解决该问题，分析算法设计思路，计算时间复杂度，并基于python编程实现\n",
    "\n",
    "e.g.:\n",
    "---\n",
    "1.\n",
    "\n",
    "<div style=\"text-align:center;width:200px;\"> <img alt=\"\" src=\"./fig/hw3q9-1.jpg\"> </div>\n",
    "输入：root = [1,3,null,null,2]， 输出为：[3,1,null,null,2]， \n",
    "\n",
    "解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。\n",
    "\n",
    "2.\n",
    "\n",
    " <div style=\"text-align:center;width:200px;\"> <img alt=\"\" src=\"./fig/hw3q9-1.jpg\"> </div>\n",
    "输入： root=[3,1,4,null,null,2]， 输出为：[2,1,4,null,null,3]\n",
    "\n",
    "解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 9  \n",
    "\n",
    "给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字：\n",
    "\n",
    "> 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。\n",
    "\n",
    "设计一个算法计算从根节点到叶节点生成的所有数字之和 ，分析算法设计思路，计算时间复杂度，并基于python编程实现\n",
    "\n",
    "叶节点:是指没有子节点的节点。\n",
    "\n",
    "e.g.:\n",
    "---\n",
    "1.\n",
    "\n",
    " <div style=\"text-align:center;width:200px;\"> <img alt=\"figure\" src=\"./fig/hw3q10-1.jpg\"> </div>\n",
    "\n",
    " 输入：root = [1,2,3], 输出：25\n",
    "\n",
    "解释：从根到叶子节点路径 1->2 代表数字 12，1->3 代表数字 13，因此和为 12 + 13 = 25 。\n",
    "\n",
    "2.\n",
    "\n",
    " <div style=\"text-align:center;width:200px;\"> <img alt=\"figure\" src=\"./fig/hw3q10-2.jpg\"> </div>\n",
    "\n",
    " 输入：root = [4,9,0,5,1], 输出：1026\n",
    "\n",
    "解释：从根到叶子节点路径 4->9->5 代表数字 495，4->9->1 代表数字 491，4->0 代表数字 40。因此和为 495 + 491 + 40 = 1026 。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 10  \n",
    "\n",
    "给你一个二叉树的根节点 root ， 检查它是否轴对称。\n",
    "\n",
    "1. 分析算法设计思路，计算时间复杂度，并基于python编程实现\n",
    "2. \\* 设计使用递归和迭代两种方法解决这个问题，计算时间复杂度，并基于python编程实现\n",
    "\n",
    "e.g.:\n",
    "---\n",
    "1.\n",
    "\n",
    " <div style=\"text-align:center;width:200px;\"> <img alt=\"figure\" src=\"./fig/hw3q11-1.png\"> </div>\n",
    "\n",
    " 输入：root = [1,2,2,3,4,4,3]， 输出：true\n",
    "\n",
    "解释：二叉树 [1,2,2,3,4,4,3] 对称。\n",
    "\n",
    "2.\n",
    "\n",
    " <div style=\"text-align:center;width:200px;\"> <img alt=\"figure\" src=\"./fig/hw3q11-2.png\"> </div>\n",
    "\n",
    " 输入：root = [1,2,2,null,3,null,3]， 输出：false"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 11  \n",
    "\n",
    "给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。\n",
    "\n",
    "此外，你可以假设该网格的四条边均被水包围。\n",
    "\n",
    "分析算法设计思路，计算时间复杂度，并基于python编程实现\n",
    "\n",
    "e.g.:\n",
    "---\n",
    "1.\n",
    "输入：grid = [\n",
    "\n",
    "    [\"1\",\"1\",\"1\",\"1\",\"0\"],\n",
    "\n",
    "    [\"1\",\"1\",\"0\",\"1\",\"0\"], \n",
    "\n",
    "    [\"1\",\"1\",\"0\",\"0\",\"0\"], \n",
    "\n",
    "    [\"0\",\"0\",\"0\",\"0\",\"0\"]  \n",
    "\n",
    "]\n",
    "\n",
    "输出：1\n",
    "\n",
    "2.\n",
    "输入：grid = [\n",
    "\n",
    "    [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "\n",
    "    [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "\n",
    "    [\"0\",\"0\",\"1\",\"0\",\"0\"],\n",
    "\n",
    "    [\"0\",\"0\",\"0\",\"1\",\"1\"]\n",
    "\n",
    "]\n",
    "\n",
    "输出：3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your code here\n",
    "# your algorithm time complexity is:"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
